#include "Greedy.h"
class Item {
    public:
    double w_;
    double v_;
    Item(double w,double v):w_(w),v_(v){};
};

int Greedy::CoinsChangeGreedy(std::vector<int>& coins,int amt) {
    int i = coins.size() - 1;
    int res = 0;
    while(amt > 0) {
        while(i > 0 && coins[i] > amt) {
            i--;
        }
        amt -= coins[i];
        res++;
    }
    return amt == 0 ? res : -1;
}

double Greedy::fractionalKnapsack(std::vector<double>& wgt,std::vector<double>& val,double cap) {
    std::vector<Item> Items;
    // 构建物品列表
    for(int i = 0; i < wgt.size();i++) {
        Items.push_back(Item(wgt[i],val[i]));
    }
    // 将物品按照单位价值从高到底排序
    std::sort(Items.begin(),Items.end(),[](Item& a,Item& b){return a.v_ / a.w_ > b.v_ / b.w_;});
    // 贪心循环选择
    double res = 0.0;
    for(auto item:Items) {
        // 如果剩余容量充足，则将当前物品全部放入背包
        if(item.w_ <= cap) {
            res += item.v_;
            cap -= item.w_;
        }
        // 如果容量不足，则将当前物品部分放入背包
        else {
            res += item.v_ / item.w_ * cap;
            break;
        }
    }
    return res;
}

int Greedy::maxCapacity(std::vector<int>& ht) {
    int i = 0;
    int j = ht.size() - 1;
    int res = 0;
    // 两指针从两端向中间靠拢
    while(i < j) {
        int cap = std::min(ht[i],ht[j]) * (j - i);
        res = std::max(cap,res);
        // 如果隔板ht[i]比ht[j]短，只有移动i才能增大容量
        if(ht[i] < ht[j]) {
            i++;
        }
        else {
            j--;
        }
    }
    return res;
}

int Greedy::maxProductCutting(int n) {
    // 当n <= 3时，必须切分出一个1
    if(n <= 3) {
        return 1 * (n - 1);
    }
    int a = n / 3;
    int b = n % 3;
    // 如果n对3取模的值 = 1,将最后一个3*1转化为2*2
    if(b == 1) {
        return std::pow(3,a - 1) * 2 * 2;
    }
    // 如果n对3取模的值 = 2,不处理
    if(b == 2) {
        return std::pow(3,a) * 2;
    }
    // 如果n对3取模的值 = 0,不处理
    return std::pow(3,a);
}